今天是紀錄LeetCode解題的第五天

第五題題目：Given a string s, return the longest palindromic substring in s.
給定一個字串s，返回字串中最長的迴文子字串

這題有非常多的解法，可以很直覺的用暴力解法列舉所有結果，也可以用中心擴展法、動態規劃，這兩種時間複雜度都是O(n²)，最好的方法是Manacher’s Algorithm，是目前最優解的演算法，但也比較複雜，今天著重介紹中心擴展法，比較簡單易懂

中心擴展法（Expand Around Center）

概念

• 迴文以「中心」為對稱點，中心可能是單一字元（奇數長度迴文），或兩個字元之間（偶數長度迴文）
• 把每個字元當作中心點往左右擴展，並檢查是否相同，如果不相同或超出範圍就跳出迴圈
• 更新最長長度

程式碼

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start = 0
        max_len = 0
        for center in range(len(s)):
            #找奇數迴文
            left = center
            right = center
            start,max_len = find(s,left,right,start,max_len)

            #找偶數迴文
            left = center
            right = center + 1   
            start,max_len = find(s,left,right,start,max_len)

        return s[start:start+max_len]

def find(s,left,right,start,max_len):
    while left >= 0 and right < len(s) and s[left] == s[right]: #判斷left,right在範圍內也就是s的長度內，並且左邊字元等於右邊字元
        if right - left + 1 > max_len: #如果目前找到的迴文子字串大於最大迴文子字串
            max_len = right - left + 1 #更新長度
            start = left
        left -= 1 #往左擴展
        right += 1 #往右擴展
    return start,max_len

執行過程

初始狀態
s = "babab"
start = 0
max_len = 0

第一次執行(center = 0,字元'b')
1.奇數迴文(left = 0, right = 0)

• while迴圈 → True (s[0]==s[0] ("b"=="b") → 長度 = 1)
• 更新：start=0, max_len=1
• 擴展：left=-1, right=1 → 停止
• 找到"b"

2.偶數迴文(left = 0, right = 1)

• s[0]!=s[1] ("b"!="a") → 不進迴圈
• 結果：start=0, max_len=1（回文 "b"）

第二次執行(center = 1,字元'a')
1.奇數迴文(left = 1, right = 1)

• while迴圈 → True (s[1]==s[1] ("a"=="a") → 長度 = 1，不比max_len = 1大)
• 擴展：s[0]==s[2] ("b"=="b") → 長度=3
• 更新：start=0, max_len=3
• 擴展：left=-1, right=3 → 停止
• 找到 "bab"

2.偶數迴文(left = 1, right = 2)

• s[1]!=s[2] ("a"!="b") → 不進迴圈
• 結果：start=0, max_len=3（回文 "bab"）

第三次執行(center = 2,字元'b')
1.奇數迴文(left = 2, right = 2)

• while迴圈 → True (s[2]==s[2] ("b"=="b") → 長度 = 1，不更新)
• 擴展：s[1]==s[3] ("a"=="a") → 長度=3,不更新
• 擴展：s[0]==s[4] ("b"=="d") → 停止
• 找到 "aba"

2.偶數迴文(left = 2, right = 3)

• s[2]!=s[3] ("b"!="a") → 不進迴圈
• 結果：start=0, max_len=3（不變）

第四次執行(center = 3,字元'a')
1.奇數迴文(left = 3, right = 3)

• while迴圈 → True (s[3]==s[3] ("a"=="a") → 長度 = 1，不更新)
• 擴展：s[2]==s[4] ("b"=="d") → 停止
• 找到 "a"

2.偶數迴文(left = 3, right = 4)

• s[3]!=s[4] ("a"!="d") → 不進迴圈
• 結果：start=0, max_len=3（不變）

第五次執行(center = 4,字元'd')
1.奇數迴文(left = 4, right = 4)

• while迴圈 → True (s[4]==s[4] ("d"=="d") → 長度 = 1，不更新)
• 擴展：s[2]==s[4] ("b"=="d") → 停止

2.偶數迴文(left = 4, right = 5)

• 超出範圍 → 停止
• 結果：start=0, max_len=3（不變）

最後回傳"bab"